package org.example.algorithm;

import org.example.path.Path;
import org.example.treasure.Treasure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class BestMoneyPath {
    int maxMoney = 0;

    public BestMoneyPath(ArrayList<Treasure> treasures, Treasure source){
        shortest(treasures,treasures.get(treasures.size() - 1));
        for (Treasure treasure : treasures) {
            treasure.isVisible = false;
        }


        source.visitedNum = 1;
        doBestMoneyPath(0,treasures,source,100,new LinkedList<>());
        for (Treasure treasure : treasures) {
            treasure.visitedNum = 0;
        }
        System.out.println(maxMoney);
//        for (Treasure vertex : treasures) {
//            System.out.println(vertex.name +" 长度："+ vertex.dist);
//        }
    }

    //迪特斯特拉算法，求0的单元最短路径集合
    public void shortest(ArrayList<Treasure> treasures,Treasure source){
        new BestLifePath(treasures,source);
    }

    public void doBestMoneyPath(int nowMoney, ArrayList<Treasure> treasures, Treasure now,int life,LinkedList<Treasure> nowRoute) {
        if(life - now.dist <= 0) return; //超时
        if(now == treasures.get(treasures.size() - 1)) {
            if (nowMoney > maxMoney){
                now.route = new ArrayList<>(nowRoute);
            }
            maxMoney = Math.max(nowMoney,maxMoney);
        } //回到终点记录最大值

        for (Path path : now.paths) {
            Treasure next = getTreasure(path.to, treasures);
            int damage = path.damage;

            if (life - damage <= 0) continue;
            if (next.visitedNum++ == 0) {
                nowRoute.add(now);
                doBestMoneyPath(nowMoney + next.value,treasures,next,life - damage,nowRoute);
            }else {
                nowRoute.add(now);
                doBestMoneyPath(nowMoney,treasures,next,life - damage,nowRoute);
            }
            next.visitedNum--;
            nowRoute.removeLast();

        }

    }
    private static Treasure getTreasure(String to,ArrayList<Treasure> graph){
        int index = to.charAt(0) - 'A';
        Treasure treasure =  graph.get(index);
        return treasure;
    }

}
